package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;

public class LeetCode_day7 {
	/**
	 * Given a set of candidate numbers (C) and a target number (T), 
	 * find all unique combinations in C where the candidate numbers sums to T.
	 * The same repeated number may be chosen from C unlimited number of times.
	 * All numbers (including target) will be positive integers.
	 * Elements in a combination must be in non-descending order.
     * The solution set must not contain duplicate combinations.
     * 
     * Each number in C must be used only once.
	 * @param candidates
	 * @param target
	 */
	public static List<Integer[]> combinationSum2(final int[] candidates, int target){
		if(candidates == null) return null;
		Arrays.sort(candidates);
		boolean[] choose = new boolean[candidates.length];
		Arrays.fill(choose, false);
		List<Integer[]> res = new ArrayList<Integer[]>();
		combinationSumBFS1(candidates, choose, 0, target, res);
		return res;
	}
	
	public static void combinationSumBFS1(final int[] candidates, boolean[] choose, int deep, int target, List<Integer[]> res){
		if(deep == candidates.length || candidates[deep] > target) return;
		else if(candidates[deep] == target){
			choose[deep] = true;
			List<Integer> list = new ArrayList<Integer>();
			for(int i = 0 ; i < deep+1 ; i++)
				if(choose[i] == true) list.add(candidates[i]);
			//check duplicates
			Integer[] newres = list.toArray(new Integer[list.size()]);
			for(Integer[] l : res){
				if(Arrays.equals(l, newres)) return;
			}
			res.add(newres);
			return;
		}else {
			//avoid duplicates, but not that useful
			/*if(deep > 1 && choose[deep] == choose[deep-1]){
				if(choose[deep-1] == true){
					boolean[] choose2 = Arrays.copyOf(choose, choose.length);
					choose2[deep] = true;
					combinationSumBFS(candidates, choose2, deep+1, target-candidates[deep], res);
				}else{
					combinationSumBFS(candidates, choose, deep+1, target, res);
				}
			}*/
			combinationSumBFS1(candidates, choose, deep+1, target, res);
			boolean[] choose2 = Arrays.copyOf(choose, choose.length);
			choose2[deep] = true;
			combinationSumBFS1(candidates, choose2, deep+1, target-candidates[deep], res);
		}
	}
	
	/**
	 * Each number is C can be used in any times. 
	 * given candidate set [2, 3, 6, 7] and target 7
	 * A solution set is:
	 * [
	 * 	[7],
	 * 	[2, 2, 3]
	 * ]
	 * @param candidates: has unique elements in non-descending order
	 * @param target
	 * @return
	 */
	public static List<List<Integer>> combinationSum1(final int[] candidates, int target){
		if(candidates == null) return null;
		List<List<Integer>> ress = new ArrayList<List<Integer>>();
		combinationSumDFS1(candidates, 0 , target, new ArrayList<Integer>(), ress);
		return ress;
	}
	
	public static void combinationSumDFS1(final int[] candidates, int deep, int target, List<Integer> res, List<List<Integer>> ress){
		if(deep >= candidates.length || candidates[deep] > target) return;
		else{
			res.add(candidates[deep]);
			if(candidates[deep] == target){
				ress.add(res);
				return;
			}else{
				int newtarget = target - candidates[deep];
				combinationSumDFS1(candidates, deep, newtarget, new ArrayList<Integer>(res), ress);
				combinationSumDFS1(candidates, deep+1, newtarget, new ArrayList<Integer>(res), ress);
			}
		}
	}
	
	/**
	 * Given an unsorted integer array, find the first missing positive integer.
	 * For example,
	 * Given [1,2,0] return 3,
	 * and [3,4,-1,1] return 2.
	 * Your algorithm should run in O(n) time and uses constant space.
	 * 
	 * !This is a wrong implementation.
	 * @param a
	 * @return
	 */
	public static int firstMissingPositive(int[] a){
		if(a == null) return -1;
		
		int minPositive = Integer.MAX_VALUE, maxPositive = 0, positiveNum = 0, realSum = 0;
		for(int i = 0 ; i < a.length ; i++){
			if(a[i] > 0){
				positiveNum++;
				realSum+=a[i];
				if(a[i] < minPositive) minPositive = a[i];
				if(a[i] > maxPositive) maxPositive = a[i];
			}
		}
		if(minPositive > 1) return minPositive-1;
		else{
			int sum = (1+positiveNum+1) * (positiveNum+1)/2;
			return sum-realSum;
		}
	}
	
	/**
	 * !Given n non-negative integers representing an elevation map where the width of each bar is 1, 
	 * compute how much water it is able to trap after raining.
	 * For example,
	 * Given [0,1,0,2,1,0,1,3,2,1,2,1,2], return 6.
	 * 
	 * For places that can hold rain, we call it bucket.
	 * One bucket has two sides
	 * One side is a local maximal.
	 * @param a
	 * @return
	 */
	public static int trappingRainWater(int[] a){
		if(a == null) return -1;
		int sum = 0, ind = 0, bucketStart = 0;
		boolean ascending = false;
		//find the first bucket
		while(ind < a.length-1 && a[ind] < 0 && a[ind+1] >= a[ind]) ind++;
		if(ind > a.length-1) return -1;
		bucketStart = ++ind;
		ind++;
		while(ind < a.length){
			if(a[ind-1] < a[ind]){
				ascending = true;
				if(ind == a.length-1){
					int min = Math.min(a[bucketStart], a[ind]);
					for(int i = bucketStart; i < ind+1 ; i++) 
						if(min > a[i]) sum += min-a[i];
				}
			}else if(a[ind-1] > a[ind]){
				if(ascending == true){
					ascending = false;
					int min = Math.min(a[bucketStart], a[ind-1]);
					for(int i = bucketStart; i < ind ; i++) 
						if(min > a[i]) sum += min-a[i];
					bucketStart = ind-1;
				}
			}
			ind++;
		}
		return sum;
	}
	
	/**
	 * Given two numbers represented as strings, return multiplication of the numbers as a string.
	 * Note: The numbers can be arbitrarily large and are non-negative.
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static String multiplyStrings(String s1, String s2){
		if(s1 == null || s2 == null || s1.isEmpty() || s2.isEmpty()) return null;
		
		StringBuilder sb = new StringBuilder();
		int more = 0 , ind1 = s1.length()-1 , ind2 = s2.length()-1;
		while(ind1 >= 0 && ind2 >= 0){
			int sum = Character.getNumericValue(s1.charAt(ind1)) + Character.getNumericValue(s2.charAt(ind2)) + more; 
			sb.insert(0, sum % 10);
			more = sum / 10;
			ind1--; ind2--;
		}
		
		if(ind1 > ind2){
			while(ind1 >= 0){
				int sum = Character.getNumericValue(s1.charAt(ind1)) + more;
				sb.insert(0, sum % 10);
				more = sum / 10;
				ind1--;
			}
		}else if(ind1 < ind2){
			while(ind2 >= 0){
				int sum = Character.getNumericValue(s2.charAt(ind2)) + more;
				sb.insert(0, sum % 10);
				more = sum / 10;
				ind2--;
			}
		}else{
			if(more != 0) sb.insert(0, more);
		}
		return sb.toString();
	}
	
	/**
	 * Given an array of non-negative integers, 
	 * you are initially positioned at the first index of the array.
	 * Each element in the array represents your maximum jump length at that position.
	 * Your goal is to reach the last index in the minimum number of jumps.
	 * For example:
	 * Given array A = [2,3,1,1,4]
	 * The minimum number of jumps to reach the last index is 2. 
	 * (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
	 * 
	 * @param a
	 * @return
	 */
	public static int jumpGameII(int[] a){
		if(a == null) return -1;
		
		int[] minimumStep = new int[]{-1};
		List<List<Integer>> ress = new ArrayList<List<Integer>>();
		List<Integer> steps = new ArrayList<Integer>();
		steps.add(0);
		jumpGameDFSII(a, 0, minimumStep, steps, ress);
		if(!ress.isEmpty()){
			for(List<Integer> res : ress){
				for(Integer i : res)
					System.out.print(i+" ");
				System.out.println();
			}
		}
		return minimumStep[0];
	}
	
	public static void jumpGameDFSII(int[] a, int currentPos, int[] minimumStep, List<Integer> steps, List<List<Integer>> ress){
		if(currentPos == a.length-1){
			if(steps.size()-1 == minimumStep[0]) ress.add(steps);
			else if(steps.size()-1 < minimumStep[0]){
				ress.clear();
				minimumStep[0] = steps.size()-1;
				ress.add(steps);
			}else if(minimumStep[0] == -1){
				minimumStep[0] = steps.size()-1;
				ress.add(steps);
			}
			return;
		}else if(currentPos > a.length - 1) return;
		else{
			if(minimumStep[0] != -1 && steps.size() > minimumStep[0]) return;
			int maxJump = a[currentPos];
			
			for(int i = 1 ; i <= maxJump ; i++){
				List<Integer> newSteps = new ArrayList<Integer>(steps);
				newSteps.add(currentPos+i);
				jumpGameDFSII(a, currentPos+i, minimumStep, newSteps, ress);
			}
			
		}
	}
	
	/**
	 * Given a collection of numbers, return all possible permutations. 
	 * 
	 * Analysis:
	 * The basic idea is that:
	 * an array without duplicates a(n) with length n
	 * 
	 * one_permutations(a(n)) = insert n to permutation(a(n-1))
	 * This leads to subproblems.
	 * Find all permutations of a(n)<-
	 * 		Find all permutations of a(n-1) & insert n into them
	 * 
	 * An other approach please see LeetCode_day8
	 * The insert method is not better than the swap.
	 * When a contains duplicates, insert method cannot generate unique set.
	 * 
	 * @param a: no duplicates
	 * @param deep
	 * @param ress
	 */
	public static void permutations1(int[] a, int deep, List<StringBuilder> ress){
		if(a == null || a.length == 0) return;
		if(deep == a.length-1){
			StringBuilder res = new StringBuilder(String.valueOf(a[deep]));
			ress.add(res);
		}else if(deep < a.length){
			permutations1(a, deep+1, ress);
			List<StringBuilder> newress = new ArrayList<StringBuilder>();
			for(StringBuilder res : ress){
				for(int i = 0 ; i <= res.length() ; i++){
					StringBuilder newres = new StringBuilder(res.toString());//not good, always new objects
					newres.insert(i, a[deep]);
					newress.add(newres);
				}
			}
			ress.clear();
			ress.addAll(newress);
			//ress = newress; incorrect, because reference won't change
		}
	}
	
	/**
	 * !You are given an n x n 2D matrix representing an image.
	 * Rotate the image by 90 degrees (clockwise).
	 * Follow up:
	 * Could you do this in-place?
	 * @param image
	 */
	public static void rotateImage(int[][] image, boolean[] choose, int i, int j, int next){
		int dim = image.length;
		if(!choose[i*dim+j]){
			int y = dim - i - 1, x = j;
			int newnext = image[x][y];
			image[x][y] = next;
			choose[i*dim+j] = true;
			rotateImage(image, choose, x, y, newnext);
		}else{
			int ind = 0;
			while(ind < choose.length && choose[ind] == true) ind++;
			if(ind == choose.length) return;
			int x = ind/dim, y = ind % dim;
			rotateImage(image, choose, x, y, image[x][y]);
		}
	}
	
	/**
	 * The key idea is to rotate the matrix according to layers. 
	 * For the nth layer(the out layer), rotate 90 degree is to move all the elements n times in a circle. 
	 * In each layer, the rotation can be performed by first swap 4 corners, 
	 * then swap 4 elements next to corner until the end of each line.
	 * @param image
	 */
	public static void rotateImage2(int[][] image){
		int n = image.length;
	    for(int i = 0; i < n/2; ++i)
	        for(int j = i; j < n-1-i; ++j){
	        	//System.out.println(i+","+j);
	        	//System.out.println((n-1-j)+","+(i));
	        	//System.out.println((n-1-i)+","+(n-1-j));
	        	//System.out.println((j)+","+(n-1-i));
	            int t = image[i][j];
	            image[i][j] = image[n-1-j][i];
	            image[n-1-j][i] = image[n-1-i][n-1-j];
	            image[n-1-i][n-1-j] = image[j][n-1-i];
	            image[j][n-1-i] = t;
	        }
	    System.out.println();
	    for(int i = 0 ; i < n ; i++){
	    	for(int j = 0 ; j < n ; j++)
	    		System.out.print(image[i][j] + ", ");
	    	System.out.println();
	    }
	}
	
	
	public static void changeReferences2(List<StringBuilder> lsit){
		List<StringBuilder> newlist = new ArrayList<StringBuilder>();
		for(StringBuilder sb : lsit)
			newlist.add(new StringBuilder(sb));
		newlist.add(new StringBuilder("new"));
		lsit = newlist;
		return;
	}
	
	public static void changeReferences3(String str){
		str = new String("new");
		return;
	}
	
	public static void changeReferences3(Integer n){
		n = new Integer(n-1);
		return;
	}
	
	public static void changeReferences3(StringBuilder n){
		n = new StringBuilder(n.toString());
		n.append("new");
		return;
	}
	
	public static void main(String[] args) {
		/*List<Integer[]> result = combinationSum2(new int[]{1,2,2,3,3,4,5,6}, 7);
		for(Integer[] res : result){
			for(Integer i : res) System.out.print(i+" ");
			System.out.println();
		}
		List<List<Integer>> result2 = combinationSum1(new int[]{2,3,6,7}, 7);
		for(List<Integer> res : result2){
			for(Integer i : res) System.out.print(i+" ");
			System.out.println();
		}
		
		System.out.println(firstMissingPositive(new int[]{1,2,0}));
		System.out.println(trappingRainWater(new int[]{0,1,0,2,1,0,1,3,2,1,2,1,2}));
		System.out.println(multiplyStrings("00123456789", "1239"));//*/
		/*System.out.println(jumpGameII(new int[]{2,3,1,1,4}));
		List<StringBuilder> ress = new ArrayList<StringBuilder>();
		permutations1(new int[]{1,2,3}, 0, ress);
		
		for(StringBuilder sb : ress)
			System.out.println(sb);
		
		List<StringBuilder> list = new ArrayList<StringBuilder>();
		list.add(new StringBuilder("hahaha"));
		
		//changeReferences(list, 1);
		changeReferences2(list);
		String str = "old";
		changeReferences3(str);
		System.out.println(str);
		Integer n = 1;
		changeReferences3(n);
		System.out.println(n);
		
		StringBuilder sb = new StringBuilder("old");
		changeReferences3(sb);
		System.out.println(sb);//*/
		
		int[][] image = new int[3][3];
		image[0] = new int[]{1,2,3};
		image[1] = new int[]{4,5,6};
		image[2] = new int[]{7,8,9};
		
		//rotateImage(image, new boolean[image.length*image.length], 0, 0, 1);
		rotateImage2(image);
		
		
		System.out.println();
	}
}
/**
 * List.toArray(new int[5]) is not correct
 * List.toArray(new Integer[5]) is correct
 * 
 * (char)49 = '1'
 * char a = 49 = '1'
 * 
 * references cannot be changed when it's a parameter of a function
 * while the content of this references can be changed.
 * See results from function series "changeReferences"
 */
